1. Field of the Invention
The invention relates to software methods and techniques for implementing an agent-oriented architecture, and more particularly to techniques for improving the interpretation phase in such an architecture.
2. References
The following documents are all incorporated by reference herein.
T. Kuhme, Adaptive Action Prompting—A complementary aid to support task-oriented interaction in explorative user interfaces. Report #GIT-GVU-93-19, Georgia Institute of Technology, Dept. of Computer Science, Graphics, Visualization, and Usability Center, 1993.
L. Balint, Adaptive Dynamic Menu System. Poster Abstracts HCI International '89, Boston, Sep. 18-22, 1989.
A. Cypher. Eager: Programming Repetitive Tasks By Example. Proc. CHI '91, pp. 33-39, 1991.
R. Beale, A. Wood, Agent-based interaction, Proceedings of HCI'94 Glasgow, 1995, pp. 239-245.
A. Wood, “Desktop Agents”, School of Computer Science, University of Birmingham, B.Sc. Dissertation, 1991.
Clarke, Smyth, “A Cooperative Computer Based on the Principles of Human Cooperation”, International Journal of Man-Machine Studies 38, pp.3-22, 1993.
N. Eisenger, N. Elshiewy, MADMAN—Multi-Agent Diary Manager, ESRC-92-7i (Economic & Social Resource Council) Internal Report, 1992.
T. Oren, G. Salomon, K. Kreitman, A. Don, “Guides: Characterizing the Interface”, in The Art of Human-Computer Interface Design, Brenda Laurel (ed.), 1990 (pp.367-381).
F. Menczer, R. K. Belew, Adaptive Infornation Agents in Distributed Textual Envirorments, Proceedings of the Second International Conference on Autonomous Agents (Agents '98), Minneapolis, Minn., May 1998.
P. Brazdil, M. Gams, S. Sian, L. Torgo, W. van de Velde, Learning in Distributed Systems and Multi-Agent Environments, Machine Learning: EWSL-91 (European Working Session on Learning), Y. Kodratoff (Ed.), Lecture Notes in Artificial Intelligence, Springer-Verlag, 1991.
B. Hodjat, M. Amamiya, The Self-organizing symbiotic agent, 1998.
P. R. Cohen, A. Cheyer, M. Wang, S. C. Baeg, OAA: An Open Agent Architecture, AAAI Spring Symposium, 1994.
S. Franklin, A. Graesser, is it an Agent or just a Program? A Taxonomy for Autonomous Agents, in: Proceedings of the Third International Workshop on Agents Theories, Architectures, and Languages, Springer-Verlag, 1996.
B. Hayes-Roth, K. Pfleger, P. Lalanda, P. Morignot, M. Balabanovic, A domain-specific Software Architecture for adaptive intelligent systems, IEEE Transactions on Software Engineering, April 1995, pp. 288-301.
Y. Shoham, Agent-oriented Programming, Artificial Intelligence, Vol. 60, No. 1, pages 51-92, 1993.
M. R. Genesereth, S. P. Ketchpel, Software Agents, Communications of the ACM, Vol. 37, No. 7, July 1994, pp. 48-53, 147.
A. Cheyer, L. Julia, Multimodal Maps: An Agent-based Approach, 1996.
T. Khedro, M. Genesereth, The federation architecture for interoperable agent-based concurrent engineering systems. In International Journal on Concurrent Engineering, Research and Applications, Vol. 2, pages 125-131, 1994.
P. Brazdil and S. Muggleton: “Learning to Relate Terms in Multiple Agent Environment”, Proceedings of Machine Learning—EWSL-91, pp. 424-439, Springer-Verlag, 1991.
S. Cranefield, M. Purvis, An agent-based architecture for software tool coordination, in Proceedings of the Workshop on Theoretical and Practical Foundations of Intelligent Agents, Springer, 1996.
T. Finin, J. Weber, G. Wiederhold, M. Genesereth, R. Fritzson, D. McKay, J. McGuire, S. Shapiro, C. Beck, Specification of the KQML Agent-Communication Language, 1993 (hereinafter “KQML 1993”) (visited 1998).
Yannis Labrou and Tim Finin, A Proposal for a new KQML Specification, TR CS-97-03, February 1997, Computer Science and Electrical Engineering Department, University of Maryland Baltimore County.
R. R. Korfhage, Information Storage and Retrieval, John Wiley & Sons, June 1997.
M. Mitchell. An Introduction to Genetic Algorithms. MIT Press, 1996.
D. C. Smith, A. Cypher, J. Spohrer, KidSim: Programming Agents without a programming language, Communications of the ACM, Vol. 37, No. 7, pages 55-67, 1994.
M. Amamiya, et al., Coordinated Morphological and Syntactic Analysis of Japanese Language, Int. Joint Conf. On Artificial Intelligence 90, pp. 1012-1017, 1990.
M. Amamiya, T. Mine:, An O(n) time and O(n2) processors parallel parsing algorithm for context-free grammars, in H. Jaakkola et al. eds., Advances in Information Modelling and Knowledge Bases, pp. 351-367, IOS Press, 1991.
N. A. Baas. Emergence, Hierarchies, and Hyper-structures. C. G. Langton ed., Artificial Life III. Addison Wesley, 1994.
N. A. Baas. Hyper-structures as Tools in Nanotechnology and Nanobiology. S. Rasmussen, S. R. Hameroff, J. Tuzinki, P. A. Hansson ed.'s, Towards a Nanobiology: Coherent and Emergent Phenomena in Bimolecular Systems. MIT Press, 1995.
J. M. Bradshaw. KaoS: An Open Agent Architecture Supporting Reuse, Interoperability, and Extensibility. Proceedings of Tenth Knowledge Acquisition for Knowledge-Based Systems Workshop, 1996.
D. Bruschi, G. Pighizzini, A Parallel Version of Earley's Algorithm, Tech Rep. 114-94, Dipartimento di Scienze dell'Informazione, Univ. of Milan, 1994.
D. Cockburn and N. R. Jennings. ARCHON: A Distributed Artificial Intelligence System for Industrial Applications. G. M. P. O'Hare, N. R. Jennings, ed's, Foundations of Distributed Artificial Intelligence. pp. 319-344. John Wiley & Sons, 1996.
J. E. Hopcroft, J. D. Ullman, Formal Languages and Their Relation to Automata, Addison-Wesley, 1969.
V. R. Lesser. Reflections on the Nature of Multi-Agent Coordination and its implications for an Agent Architecture, Autonomous Agents and Multi-Agent Systems. pp. 89-111, Kluwer Academic Publishers, 1, 1998.
A. G, Manousopoulou, G. Papakonstantinou, P. Tsanakas, A chart-like parser for context sensitive grammars, Proceedings of the 1st workshop on tabulation in parsing and deduction (TAPD '98), pp. 89-95, Paris, France, 1998.
D. Martin and D. Moran. Building distributed software systems with the open agent architecture. Proc. of the Third International Conference on the Practical Application of Intelligent Agents and Multi-Agent Technology. The Practical Application Company Ltd., Blackpool, Lancashire, UK, March 1998.
3. Description of Related Art
Most human-machine interfaces in use today are relatively complicated and difficult to use. In U.S. patent application Ser. No. 09/183,764, filed Oct. 30, 1998, incorporated by reference herein, there is described a method for processing a message, by a network of agents each of which has a view of its own domain of responsibility. The method typically involves two main phases: an interpretation phase and a delegation phase. In the interpretation phase, an initiator agent which receives an input request and does not itself have a relevant interpretation policy, queries its downchain agents whether the queried agent considers such message, or part of such message, to be in its domain of responsibility. Each queried agent recursively determines whether it has an interpretation policy of its own that applies to the request, and if not, further queries its own further downchain neighboring agents. The further agents eventually respond to such further queries, thereby allowing the first-queried agents to respond to the initiator agent. The recursive invocation ofthis procedure ultimately determines a path, or a set of paths, through the network from the initiator agent to one or more leaf agents. In the event of a contradiction, the network is often able to resolve many of such contradictions according to predetermined automatic algorithms. If it cannot resolve a contradiction automatically, it learns new interpretation policies necessary to interpret the subject message properly. Such learning can include interaction with a user, and can be designed to localize the learning as closely upchain to the correct leaf agent in the network as possible. After the appropriate paths through the network are determined, in the delegation phase the request is then transmitted down each determined path, with each agent along the way taking any local action thereon and passing the message on to the next agent in the path.